Prime Number Theorem

The prime number theorem may refer to any one of many different results estimating the prime counting function \(\pi\). Here we present the most commonly stated version, and one of the weaker versions.

Theorem
\[ \pi(x) \sim \frac{x}{\log x}\]

This claim is simply that the relative error between \(\pi(x)\) and \(\frac{x}{\log x}\) tends to \(0\). This makes no claim about the absolute error \(\pi(x) - \frac{x}{\log x}\), for which better results exist, as well as better approximating functions.

The prime number theorem, as proven here, is merely a consequence of a closely related result for the second Chebyshev function. As such, the main work involved in proving the theorem comes from that that theorem. Here we just show that they are equivalent.

Theorem
\[ \psi(x) \sim x \iff \pi(x) \sim \frac{x}{\log x}\]
Proof

From this result we have

\[ \psi(x) = \sum_{p \leq x} \log p \left\lfloor \frac{\log x}{\log p}\right\rfloor \leq \sum_{p \leq x} \log p \frac{\log x}{\log p} = \sum_{p \leq x} \log x = \pi(x) \log x.\]

For a lower bound, we have for any \(\epsilon \in (0, 1)\)

\[\begin{align*} \psi(x) &\geq \sum_{x^{1 - \epsilon} \leq p \leq x} \log p \\ &\geq \sum_{x^{1 - \epsilon} \leq p \leq x} \log(x^{1 - \epsilon}) \\ &= (1 - \epsilon) \log x (\pi(x) - \pi(x^{1 - \epsilon})) \\ &= (1 - \epsilon) \log x (\pi(x) + O(x^{1 - \epsilon})) \\ &= \pi(x)\log(x) + O(x^{1 - \epsilon}) \\ \end{align*}\]

noting that \(\log x = O(x^{1 - \epsilon})\).

Combining these and dividing by \(x\) gives the inequality

\[ \frac{\pi(x) \log x}{x} \leq \frac{\psi(x)}{x} \leq \frac{\pi(x) \log x}{x} + O(x^{-\epsilon}).\]

It is then clear by the pinching theorem that the prime number theorem implies \(\psi(x) \sim x\) because \(\lim_{x \to \infty} O(x^{-\epsilon}) = 0\).

For the reverse implication, we can derive from the above inequality

\[ \frac{\psi(x)}{x} + O(x^{-\epsilon}) \leq \frac{\pi(x) \log x}{x} \leq \frac{\psi(x)}{x}\]

and again the result follows from the pinching theorem.

Corollary
\[ \pi(x) \sim \mathrm{Li}(x)\]
Proof

First note that we have by direct comparison that

\[ \mathrm{Li}(x) = \int_2^x \frac{\mathrm{d}t}{\log t} \leq \int_2^x \frac{\mathrm{d}t}{t} = \log x - \log 2\]

and thus \(\mathrm{Li}(x) \to \infty\) as \(x \to \infty\).

Hence by L'Hopital's Rule and the fundamental theorem of calculus we have

\[\begin{align*} \lim_{x \to \infty} \frac{\mathrm{Li}(x)}{x/\log(x)} &= \lim_{x \to \infty} \frac{\frac{1}{\log x}}{\frac{1}{(\log x)} - \frac{1}{(\log x)^2}} = \lim_{x \to \infty} \frac{1}{1 - \frac{1}{\log x}} = 1. \end{align*}\]